Introduction to Machine Learning

1. Introduction

This unit continues the evaluation story from Unit 24, now introducing extrinsic clustering evaluation measures — Purity, the Rand Index, and the Jaccard Coefficient — then switches to a fundamentally different clustering algorithm: DBSCAN. We will see how DBSCAN discovers clusters of arbitrary shape and explicitly flags noise/outlier points, and we will study how to select its hyperparameters MinPts and \( \varepsilon \) (epsilon) via the K-distance graph.

Today's Agenda

1. Recap of Silhouette Coefficient & average silhouette width
2. Extrinsic measures: Purity, Rand Statistic (RI), Jaccard Coefficient
3. DBSCAN algorithm & its point taxonomy
4. Definitions: directly density-reachable, density-reachable, density-connected
5. Identifying optimal ε and MinPts: rule-of-thumb & K-distance graph / elbow
6. K-distance graph example on Iris dataset
7. DBSCAN vs K-Means comparison

2. Theory

2.1 Silhouette Recap (from Unit 24)

For each object \( d_i \in C_i \), compute its per-cluster average silhouette width: \[ \bar{s}(C_j) = \frac{1}{|C_j|} \sum_{d_i \in C_j} s(i) \] and the global average silhouette width: \[ \text{ASW} = \frac{1}{n} \sum_{i=1}^{n} s(i) \] Computationally, silhouette is expensive for large datasets (O(n²) distance evaluations).

2.2 Extrinsic Clustering Evaluation Measures

Extrinsic measures require ground-truth labels and compare a generated clustering against these labels. They enable head-to-head comparison of algorithms on benchmark datasets where labels exist. We cover three: Purity, Rand Index, Jaccard.

2.3 Purity Contingency Table Example

6 clusters × 6 ground-truth labels on a news-like dataset (3,204 documents):

For each cluster row, take the maximum and divide by n:

2.4 Rand Index Calculation: 5-Point Worked Example

Five data points: p1, p2, p3, p4, p5.
Produced clustering: C1 = {p1, p2, p3}, C2 = {p4, p5} (two clusters).
True labels: L1 = {p1, p2}, L2 = {p3, p4, p5} (two classes).

Total pairs of distinct points: C(5,2) = 10 pairs.

Counts: TP = 2, TN = 5, FP = 2, FN = 1. Total 10.

2.5 DBSCAN — Density-Based Spatial Clustering of Applications with Noise

DBSCAN classifies every data point into exactly one of three categories, based on two hyperparameters: the radius ε (epsilon) and the neighbor count MinPts.

2.6 DBSCAN Key Definitions

1. Directly density-reachable: p is directly density-reachable from q if:
   • q is a core point, AND
   • p is within ε of q (p ∈ N_ε(q)).
   Note: "directly reachable" is NOT symmetric. A core can reach a border, but a border cannot reach back because borders aren't core points.
2. Density-reachable: p is density-reachable from q if there exists a chain of points q → q₁ → q₂ → … → q_k → p such that each adjacent step is directly density-reachable. Still asymmetric in general.
3. Density-connected: p and q are density-connected if there exists some core point o such that BOTH p and q are density-reachable from o. Symmetric! Captures the "same cluster" relationship.
4. A DBSCAN cluster: A maximal set of density-connected points.

2.7 DBSCAN Example 1: Manual Execution

5 2D points: A(1,4), B(2,3), C(1,5), D(5,5), E(8,1).
MinPts = 2, ε = 2 (Euclidean distance used).

Step 0: Find cores. For each point, count its ε-neighbors (distance ≤ 2):

• A(1,4): dist to B = √((1)²+(-1)²)=√2≈1.41; to C=√(0+1)=1.0; to D=√16+1≈4.12; to E≈√58≈7.6. Neighborhood: {A,B,C} (size 3 ≥ 2). → A is CORE.
• B(2,3): to A≈1.41, to C=√(1+4)=√5≈2.24 >2, to D≈3.6, to E≈6.3. Neighborhood: {B,A} (size 2 ≥ 2). → B is CORE? Actually count includes B itself = 2 → Yes, CORE.
• C(1,5): to A=1.0, to B≈2.24, to D≈4.0. Neighborhood: {C,A}=2 → CORE.
• D(5,5): to A≈4.12, to B≈3.6, to C≈4.0, to E≈5.0. Neighborhood: {D}=1 < 2 → NOT core.
• E(8,1): distances huge. Only itself → NOT core.

Step 1: Grow clusters from cores.

1. Start with core A → Create Cluster 1. Add A. Expand to B (directly reachable) and C (directly reachable). Done (B and C, while cores, have no new points within ε).
2. D has no other neighbors besides itself → mark as noise.
3. E has no other neighbors besides itself → mark as noise.

2.8 Selecting DBSCAN Hyperparameters

Selecting MinPts

• Rule of thumb: MinPts ≥ (dimensionality + 1), where d = number of features.
• For 2D data: MinPts ≥ 3 (common pick: 4).
• For higher dimensions: MinPts ≥ 4 or 5 as a start.
• Larger MinPts:
  • More robust to noise/outliers.
  • May merge smaller dense patches (loss of granularity).
• Standard starting heuristic: MinPts = 4 or 5, then tune.

Selecting ε via the K-Distance Graph

For each point in the dataset, compute the distance to its k-th nearest neighbor, with k = MinPts (or k = MinPts − 1 depending on convention). Then sort all these k-distances in ASCENDING order and plot. Use the elbow of this curve as ε.

• Points in dense regions (cluster members): k-th nearest neighbor is close → small k-distance.
• Points in sparse regions (outliers / noise): k-th nearest neighbor is far → large k-distance.
• Elbow: transition region where distances "jump" from small (inliers) to large (outliers). Choose ε at that jump.

Iris K-distance Graph Case Study

• With eps=0.2 and MinPts=5 on scaled Iris: all points become noise (label=-1) → ε is too small.
• Using k-distance elbow method on Iris (k ≈ MinPts−1): pick ε ≈ 0.8 at the bend.
• Running DBSCAN with ε=0.8, MinPts=5: two clusters discovered with very few noise points.
• Why 2 clusters instead of 3? PCA visualization of Iris confirms two major dense regions in feature space; Setosa is well-separated from Versicolor + Virginica which partially overlap.

2.9 DBSCAN vs K-Means: Side-by-Side

3. Interactive Examples

4. Numerical Solutions

5. Try It Yourself

6. Interactive Quiz